package exam.test18.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Endstart
 * Date: 2020-12-18
 * Time: 23:18
 */
public class Check {


    static class Node {
        int element;
        Node leftNode;
        Node rightNode;

        Node(int data) {
            this.element = data;
        }

    }

    public void subTreeCheck(Node root) {
        int leftSum = nodeSum(root.leftNode);
        int rightSum = nodeSum(root.rightNode);
        if (leftSum < rightSum) {
            rebuildNode(root.leftNode, leftSum);
        }
        if (leftSum > rightSum) {
            rebuildNode(root.rightNode, rightSum);
        }
    }

    private void rebuildNode(Node subNode, int sumTotal) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(subNode);
        while (queue.isEmpty() == false) {
            Node nodeTmp = queue.poll();
            if (nodeTmp == null) {
                continue;
            }
            nodeTmp.element = sumTotal--;
            queue.offer(nodeTmp.leftNode);
            queue.offer(nodeTmp.rightNode);
        }
    }

    private int nodeSum(Node node) {
        return sumRecursive(node, 0);
    }

    private int sumRecursive(Node node, int sum) {
        if (node == null) {
            return sum;
        }
        sum += node.element;
        sum = sumRecursive(node.leftNode, sum);
        return sumRecursive(node.rightNode, sum);
    }
}
